# 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，
# 每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
# 例如 a b c e
#      s f c s
#      a d e e
# 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，
# 路径不能再次进入该格子。


# 说明：matrix是传入的矩阵，
#       rows和cols是给定的矩阵的长宽信息，用于告诉你矩阵是几乘几的
#       path其实是那个字符串，也可以看作是路径
class Solution:
    def hasPath(self, matrix, rows, cols, path):
        index = [False] * (len(matrix))
        for i in range(rows):
            for j in range(cols):
                if self.get_path(matrix, rows, cols, path, i, j, index,0):
                    return True
        return False

    # 最开始是可以向最多四个方向探索的，然后的每一次其实最多只能向三个方向探索
    # 可以用一个和原始矩阵大小一样的bool矩阵存储每一步，走过的就是True，就不能再回头了
    def get_path(self, matrix, rows, cols, path, i, j, index_matrix, k):
        index = i * cols + j

        # 不能超过上下左右边界
        if j < 0:
            return False
        if j >= cols:
            return False
        if i < 0:
            return False
        if i >= rows:
            return False
        if index_matrix[index] == True:
            return False
        if matrix[index] != path[k]:
            return False
        if k==len(path)-1:  # 走到这里就说明最后一个元素也匹配了，就返回True
            return True
        index_matrix[index] = True
        if self.get_path(matrix, rows, cols, path, i - 1, j, index_matrix, k + 1) or self.get_path(matrix, rows, cols, path, i + 1, j, index_matrix, k + 1) or self.get_path(matrix, rows, cols, path, i , j-1, index_matrix, k + 1) or self.get_path(matrix, rows, cols, path, i , j+1, index_matrix, k + 1):
            return True
        index_matrix[index] = False
        return False
